import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-31
 * Time: 9:57
 */

public class Solution {

    /**
     *  方法一: 递归
     *  判断当前是否是后序遍历, 再判断左右子树是不是后序遍历
     * @param postorder
     * @param left
     * @param right
     * @return
     */
    public boolean isPostorder(int[] postorder, int left, int right) {
        if (left >= right){
            return true;
        }
        // 对后序遍历进行左右子树分割
        int value = postorder[right];
        int mid = right - 1;
        // 先找右子树
        while (mid >= left && postorder[mid] > value) {
            mid--;
        }
        int cur = mid;
        // 如果左子树中还有比 value 大的, 说明就不是后序遍历
        while (cur >= left) {
            if (postorder[cur] > value) {
                return false;
            }
            cur--;
        }
        // 同时左右子树都是后序遍历, 则返回 true
        return isPostorder(postorder, left, mid) && isPostorder(postorder, mid+1, right-1);
    }

    public boolean verifyPostorder(int[] postorder) {
        return isPostorder(postorder, 0, postorder.length - 1);
    }


    /**
     *  方法二:  单调栈
     *  整个过程有点类似于回溯, 就是不断变化根的过程
     *  后序遍历逆过来, 就是 根, 右, 左
     *  那么 arr[i] < arr[i+1], 那么arr[i+1] 就是 arr[i] 的右子节点
     *  arr[i] > arr[i+1], 开始减小了, 那么 arr[i+1]一定是最开始的那个左子节点
     *  那 arr[i+1] 的根是哪个呢, 是它前面比他大的中最小的那个
     *  但是由于那个节点都会入栈做栈顶, 所以就不用考虑坐标了
     *  这样就可以利用单调栈
     *  不管在哪个小子树上面找, 我们都是先右, 后左,
     *  注意右(右子树)边的值一定没有左(左子树)边的大, 越往右, 值越小
     *  那么只要已经找到左子树了, 后面还有比根大的, 那么就不是后序遍历
     * @param postorder
     * @return
     */
    public boolean verifyPostorder2(int[] postorder) {
        // 栈中保存的根, 上面的根都在栈底部存着
        // 整个过程有点类似于回溯
        Stack<Integer> singleStack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            if (postorder[i] > root) {
                return false;
            }
            // 遇到开始降序了, 说明遇见左子树了, 那么就开始找左子树的根
            // 注意右边的值一定没有左边的大, 所以不管怎么样, 右边的值不可能比根大, 否则就是不符合条件
            while (!singleStack.isEmpty() && singleStack.peek() > postorder[i]) {
                // 它的根是前面比他大的中最小的那个
                root = singleStack.pop();
            }
            // 不管是哪个节点, 当前的这个节点一定是会入栈的
            // 所以它后面的那个值一定是会跟他比较的
            singleStack.add(postorder[i]);
        }
        return true;
    }


    /**
     *  方法三: 重建这颗二叉搜索树
     *  但是并没有真正的重建
     *  只是通过上下界来判断当前下标元素是否满足条件
     *  最终通过是否匹配完来判断是否是后序遍历
     */
    public int end;
    public boolean verifyPostorder3(int[] postorder) {
        this.end = postorder.length - 1;
        judge(postorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
        return end < 0;
    }

    private void judge(int[] postorder, int minValue, int maxValue) {
        if (end < 0) {
            return ;
        }
        int cur = postorder[end];
        // 判断是否满足条件
        if (cur > minValue && cur < maxValue) {
            // 只有当前位置满足限定条件再判断下一个位置
            end--;
            // 右子树
            judge(postorder, cur, maxValue);
            // 左子树
            judge(postorder, minValue, cur);
        }
    }
}
